package toutiao.solution2018;

import java.util.*;

/**
 *给一个二维平面，而且横纵坐标都不会重复（简化了排序），要求“不存在左上方还有点”的点集。
 * 因为数据量最大是50W，所以基本上用是O(nlogn)的方法解决。
 * 首先按x坐标排个序（因为y不重复所以不用管），
 * 然后从后往前（此时保证当前点的x是比后面的x要小的），记录一个当前最大的Y，
 * 如果当前这个位置的y比Y还要大，那么明显这个位置的“左上方”不可能有点了。
 * 问题解决。
 */
public class SolutionA {

    public  List<Point> maxPoints(int[] x, int[] y, int n) {
        Point[] points = new Point[n];
        for (int i = 0; i < n; i++) {
            points[i] = new Point(x[i], y[i]);
        }
        Arrays.sort(points, new myComparator());
        List<Point> list = new ArrayList<>();
        int maxY = Integer.MIN_VALUE;
        for (int i = n-1; i>=0;i--) {
            if (points[i].y > maxY) {
                maxY = points[i].y;
                list.add(points[i]);
            }
        }
        list.sort(new myComparator());
        return list;
    }

    class  myComparator implements Comparator<Point>{

        @Override
        public int compare(Point o1, Point o2) {
            return o1.x - o2.x;
        }
    }

    class Point {
        int x;
        int y;
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] x = new int[n];
            int[] y = new int[n];
            for (int i = 0; i < n; i++) {
                x[i] = sc.nextInt();
                y[i] = sc.nextInt();
            }
            List<Point> list = new ArrayList<>();

            list = new SolutionA().maxPoints(x, y, n);
            for (Point aList : list) {
                System.out.println(aList.x + " " + aList.y);
            }
        }
    }
}
